package com.cqs.leetcode.dp;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixqw
 * @date 2020/8/23
 */
public class Triangle120 {


    public int minimumTotal0(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;
        int rows = triangle.size();
        int maxCols = triangle.get(rows - 1).size();
        int[][] result = new int[triangle.size()][maxCols];
        result[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> list = triangle.get(i);
            for (int j = 0; j < list.size(); j++) {
                int left = j == 0 ? Integer.MAX_VALUE : result[i - 1][j - 1];
                int right = j == i ? Integer.MAX_VALUE : result[i - 1][j];
                result[i][j] = Math.min(left, right) + list.get(j);
            }
        }

        int min = result[rows - 1][0];
        for (int i = 1; i < maxCols; i++) {
            if (result[rows - 1][i] < min) {
                min = result[rows - 1][i];
            }
        }
        return min;
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;
        int rows = triangle.size();
        int maxCols = triangle.get(rows - 1).size();
        int[] result = new int[maxCols];
        result[0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            List<Integer> list = triangle.get(i);
            int left = result[0];
            result[0] += list.get(0);
            for (int j = 1; j < list.size(); j++) {
                int right = j == i ? Integer.MAX_VALUE : result[j];
                int cur = Math.min(left, right) + list.get(j);
                //保存现场
                left = result[j];
                //更新结果
                result[j] = cur;
            }
        }
        int min = result[0];
        for (int i = 1; i < result.length; i++) {
            if (min > result[i]) {
                min = result[i];
            }
        }
        return min;
    }



    public static void main(String[] args) {
        Triangle120 triangle = new Triangle120();
        List<List<Integer>> test = Lists.newArrayList(
                Lists.newArrayList(2),
                Lists.newArrayList(3,4),
                Lists.newArrayList(6,5,7),
                Lists.newArrayList(4,1,8,3)
        );
        int i = triangle.minimumTotal(test);
        System.out.println(i + "\t" );
    }


}
